def heap_sort(nums):
    n = len(nums)
    maxHeap(nums, n)

    left = n - 1
    while left>0:
        t = nums[left]
        nums[left] = nums[0]
        nums[0] = t
        
        left = left - 1
        i = 0
        while i<left - 1:
            c1Idx = 2*i+1
            c2Idx = 2*i+2

            if c1Idx>left -1:
                break

            if c2Idx>left -1:
                largeCIdx = c1Idx

            elif nums[c1Idx]<nums[c2Idx]:
                largeCIdx = c2Idx
            else:
                largeCIdx = c1Idx

            if nums[i]>=nums[largeCIdx]:
                break

            t = nums[i]
            nums[i]=nums[largeCIdx]
            nums[largeCIdx]=t

            i = largeCIdx


    
def maxHeap(nums, n):
    for i in range(1, n):
        currentp = int((i - 1)/2)
        current = i

        while nums[current]>nums[currentp]:
            
            t = nums[current]
            nums[current]=nums[currentp]
            nums[currentp]=t

            current = currentp
            currentp = int((current-1)/2)
            if currentp < 0:
                break


nums = [3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6]
# nums=[2,3,1,2,5,4,6,1]
# nums=[2,3,1,4]
heap_sort(nums)
print(nums)